#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

vector<int> arr = { 6,0,8,4,1,2,9,7,5,6,4,8,4,4,5,0,7,1 };

void QuickSort(vector<int>& arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	int key = arr[rand() % (right - left + 1) + left];
	int cur = left;
	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			swap(arr[cur++], arr[left++]);
		}
		else if (arr[cur] > key)
		{
			swap(arr[cur], arr[right--]);
		}
		else
		{
			cur++;
		}
	}
	QuickSort(arr, begin, left - 1);
	QuickSort(arr, right + 1, end);
}

void test_quicksort()
{
	vector<int> a = arr;

	srand(time(nullptr));
	QuickSort(a, 0, a.size() - 1);

	for (auto& e : a)
	{
		cout << e << ' ';
	}
	cout << endl;
}

void MergeSort(vector<int>& arr, int left, int right, vector<int>& tmp)
{
	if (left >= right)
	{
		return;
	}

	int mid = (left + right) / 2;
	MergeSort(arr, left, mid, tmp);
	MergeSort(arr, mid + 1, right, tmp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

void test_mergesort()
{
	vector<int> a = arr;
	vector<int> tmp(a.size());
	MergeSort(a, 0, a.size() - 1, tmp);

	for (auto& e : a)
	{
		cout << e << ' ';
	}
	cout << endl;
}

int main()
{
	//test_quicksort();
	test_mergesort();
	return 0;
}

//1 2 3 4 5 6 7 8 9 10